package offer;

/**
 * @Author Elephas
 * @Date 2022/1/18
 **/
public class SearchRange {
    public static void main(String[] args) {
        final int[] TEST01 = new int[]{2,2};
        new SearchRange().searchRange(TEST01,3);
    }
    /*
        算法思想：基于二分查找
     */
    public int[] searchRange(int[] nums,int target){
        // 判定是否存在 target 元素
        if(nums.length < 1){
            return new int[]{-1,-1};
        }
        int pos = binarySearch(nums,target);
        if(pos == -1){
            return new int[]{-1,-1};
        }else{
            // 寻找左侧边界
            int leftBound = findLeftBound(nums,target,pos);
            // 寻找右侧边界
            int rightBound = findRightBound(nums,target,pos);
            return new int[]{leftBound,rightBound};
        }

    }
    public int findLeftBound(int[] nums, int target, int upper){
        int left = 0,right = upper;
        int mid = left + (right - left) / 2;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                right--;
            }else {
                // 因为这是一个递增数组，所以左侧的值必定小于等于 target
                left = mid + 1;
            }
        }
        return left;
    }
    public int findRightBound(int[] nums,int target,int lower){
        int left = lower,right = nums.length - 1;
        int mid = left + (right - left) / 2;
        while( left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                left++;
            }else {
                // 因为这是一个递增数组，所以右侧的值必定大于等于 target
                right = mid - 1;
            }
        }
        return right;
    }
    public int binarySearch(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        int mid = left + (right - left) / 2;
        while(left <= right){
            mid = left + (right - left) / 2;
            if( nums[mid] == target){
                break;
            }else if( nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        if(left <= right){
            return mid;
        }else{
            return -1;
        }
    }

}
